# 岛屿数量： https://leetcode-cn.com/problems/number-of-islands/

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
            没想到使用图算法解决： 深度优先遍历
        """
        def dfs(grid, i, j):
            if grid[i][j] == '0':
                return 
            # 置为 0
            grid[i][j] = '0'

            # 向四个方向
            if j > 0: # 左
                dfs(grid, i, j - 1)
            if i > 0: # 上
                dfs(grid, i - 1, j)
            if j < len(grid[0]) - 1: # 右
                dfs(grid, i, j + 1)
            if i < len(grid) - 1: # 下
                dfs(grid, i + 1, j)
            
        n = len(grid)
        m = len(grid[0])
        cnt = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == "1":
                    dfs(grid, i, j)
                    cnt += 1

        return cnt

